-- la idea es que dado el un entero x una lista de monedas, se generan todas las listas que pueden generar el cambio x y luego controlo
-- cual lista dentro de la lista de solucines posibles a x es la de menor longitud.

-- la funcion cambio lo que hace es calcular el el cambio posible a devolver
cambio :: Int -> [Int] -> [Int]
cambio 0 (x:xs) = []
cambio n (x:xs) = vc : cambio v  (x:xs)
							where
							vc = verificar n (x:xs)
							v = n - vc 
-- la funcion verificar lo que hace es controlar que la moneda obtenida del conjunto no sea mayor al valor del entero.
verificar :: Int -> [Int] -> Int
verificar m [] = error "No hay monedas"
verificar m (x:xs) | (x <= m) = x
				   | otherwise = verificar m xs

-- hasta ahi seria greedy

darCambio :: [(Int,Int)] -> Int -> [Int]
darCambio [] n = error "No hay monedas"
darCambio ((d,c):xs) n	| d > n || c <= 0 = darCambio xs n
						| d == n = [d]
						| d < n = d : darCambio ((d,c-1):xs) (n-d)



-----------------------------------------------------
-- la funcion cantidad monedas lo que hace es retornar la lista de menor longitud
cantidadMonedas :: [Int] -> [[Int]] -> [Int]
cantidadMonedas x [[]] = x
cantidadMonedas x (y:xs) | length x < length y = cantidadMonedas x xs
						 | otherwise = cantidadMonedas y xs

-- la funcion generar lista cambio va armando la lista de listas de posibles soluciones al cambio x
generarListasCambio :: Int -> [Int] -> [[Int]]
generarListasCambio n [] = [[]]
generarListasCambio n (x:xs) = cambio n (x:xs) : generarListasCambio n xs

-- la funcion listaCambioFinal es la emcargada de retornar cual lista de minima longitud es la que da solucion al entero x
listaCambioFinal :: Int -> [Int] -> [Int]
listaCambioFinal n (x:xs) = cantidadMonedas  y ys
							where
							y = head (generarListasCambio n (x:xs))
							ys = tail (generarListasCambio n (x:xs))


